package basic.study.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @ClassName Hard23
 * @Description
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/18 13:09
 * @Version 1.0
 */
public class Hard23 {
    /**
     * 分治解法
     */
    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length == 0) return null;
            return merge(lists, 0, lists.length - 1);
        }


        private ListNode merge(ListNode[] lists, int left, int right) {
            if (left == right) return lists[left];
            int mid = left + (right - left) / 2;
            ListNode l1 = merge(lists, left, mid);
            ListNode l2 = merge(lists, mid + 1, right);
            return mergeTwoLists(l1, l2);
        }

//        private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//            if (l1 == null) return l2;
//            if (l2 == null) return l1;
//            if (l1.val < l2.val) {
//                l1.next = mergeTwoLists(l1.next, l2);
//                return l1;
//            } else {
//                l2.next = mergeTwoLists(l1,l2.next);
//                return l2;
//            }
//        }


        private ListNode mergeTwoLists(ListNode a, ListNode b) {
            if ((a == null) || (b==null)) {
                return a != null? a: b;
            }
            ListNode solder = new ListNode(-1);
            ListNode node = solder;
            while (a != null && b != null) {
                if (a.val < b.val) {
                    node.next = a;
                    a = a.next;
                } else {
                    node.next = b;
                    b = b.next;
                }
                node = node.next;
            }
            node.next = (a != null)?a:b;
            return solder.next;
        }

    }

    /**
     * 优先队列解法
     */
    class Solution1 {
        Comparator<ListNode> cmp = new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        };

        public ListNode mergeKLists(ListNode[] lists) {

            PriorityQueue<ListNode> queue = new PriorityQueue<>(cmp);
            for (ListNode list: lists) {
                if (list != null) {
                    queue.add(list);
                }
            }
            ListNode solder = new ListNode(-1);
            ListNode node = solder;
            while (!queue.isEmpty()) {
                ListNode temp = queue.poll();
                node.next = temp;
                node = node.next;
                if (temp.next != null) {
                    queue.offer(temp.next);
                }
            }
            return solder.next;
        }
    }





    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
}
